package Leetcode.StackAndQueue.trapWater42;

/**
 * 动态规划 来自官方题解
 * rightMax存储的数值是从左向右遍历最大的值 leftMax是从右向左
 * 则对每个下标为i的位置都知道其左右边界，即可求得结果
 *
 * 该方法最为简单明了
 */
public class Solution3 {
    public int trap(int[] height) {
        int result = 0;
        int len = height.length;
        if(len == 0) {
            return result;
        }
        int[] rightMax = new int[len];
        int[] leftMax = new int[len];
        rightMax[0] = height[0];
        leftMax[len - 1] = height[len - 1];
        for(int i = 1; i < len; i++) {
            rightMax[i] = height[i];
            rightMax[i] = Math.max(rightMax[i] , rightMax[i - 1]);
        }
        for(int i = len - 2; i >= 0; i--) {
            leftMax[i] = height[i];
            leftMax[i] = Math.max(leftMax[i] , leftMax[i + 1]);
        }
        for(int i = 0; i < len; i++) {
            result += Math.min(leftMax[i],rightMax[i]) - height[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {0,1,0,2,1,0,1,3,2,1,2,1};
        Solution3 solution = new Solution3();
        System.out.println(solution.trap(nums));
    }
}
